Code and Notes (Week 5 Thursday)

The C-Machine Plus rule is:

(Plus □ e) ▷ s ≺ v |->C (Plus v □) ▷ s ≻ e

E-Machine Plus rule is essentially the same:

(Plus □ e) ▷ s | η ≺ v |->E (Plus v □) ▷ s | η ≻ e

To prove simulation here, we would have to think about how our A
abstraction function performs a substitution to all the elements
in the E-Machine. There is only one candidate environment here,
η, so it will be applied everywhere to the expression e. The value
forms v are unaffected by substitution (which is crucial, since
they need to be passed out of functions).

So, after some thinking about what the abstraction does, we realise
that the E-Machine rule performs the same step as the C-Machine rule.

We had to think a little about all the rules to answer the question of which E-Machine rule does not correspond to a C-Machine rule.

It is the one that encounters an environment on the stack. The C-Machine stack does not have the environment entries. So, the equivalent M-Machine step is a no-op. Again, we need to think about what our A abstraction function does. The current environment η is used as a substitution for an expression (in s ≻ e mode), but in this case we are returning a value (in s ≺ v mode). It also used as a substitution for elements in the stack until another environment is encountered. So, in this case, it is not used, and the stack pop really is a no-op.

Here is some Haskell code that shows off the laziness of the language.

Haskell uses a "call by need" semantics, where all values are left unevaluated until they are needed. Need for a value includes using it in basic operations (e.g. computing x + 1 forces x to be evaluated) and pattern matching on it.

The pattern matching case is interesting. When the "take2" function below pattern-matches "xs" against the case "Cons tl hd", this forces "xs" to be evaluated enough to know whether it is a "Nil" or a "Cons". In the "Cons" case, however, the "tl" and "hd" elements are themselves lazy.

This allows us to construct unusual functions like "iterate" from the standard library and "iterate2" below. These functions never return a completed list. So, an attempt to compute their length will never finish. In a lazy language, you can call such a nonterminating function and not use the result. In a language like Haskell that is lazy at every "Cons" site, you can safely take a prefix of the infinite list with "take" or "take2". What is happening is that each pattern match on "iterate2 f x" forces the execution one step further (constructing a "Cons") but leaves the two arguments of the "Cons" lazy. If we only need a finite amount of the contents of the infinite list to calculate something, then our computation will terminate.

data List2 a =
  Cons (List2 a) a
  | Nil
  deriving (Show, Eq)

iterate2 :: (a -> a) -> a -> List2 a
iterate2 f x = Cons (iterate2 f (f x)) x

take2 :: Int -> List2 a -> List2 a
take2 i xs = if i <= 0 then Nil
  else case xs of
    Nil -> Nil
    Cons tl hd -> Cons (take2 (i - 1) tl) hd


-- Haskell has "Call By Need" semantics.

f :: Int -> Int
f x = f x

g :: Int -> Int
g x =
  let y = f x in
  x + 12

-- lambdas create thunks in any functional language

l x = (\y -> x + 1)

-- In Haskell, Ints also create thunks
-- (the implementation usually optimises this away)


-- In particular, for Cons :: Int -> List Int -> List Int,
-- each of the cells can be a thunk.



-- zip can be demoed like this:
-- zip [1 .. 20] (iterate (* 2) 1)


fib :: [Integer]
fib = [1, 1] ++ [a + b | (a, b) <- zip fib (drop 1 fib)]


-- This is showing off the variant evaluation orders of
-- similar looking languages. MinHS doesn't have any of
-- these tricky features. Neither does OCaml.